#pragma once
#include <iostream>
#include <vector>
#include <random>
#include <string>
#include <cstring>

namespace cr
{
    template <class Comp = std::less<int>>
    class Sort
    {
    private:
        int Myrandom(int min, int max)
        {
            // 随机数引擎，使用硬件随机设备作为种子
            std::random_device rd;
            std::mt19937 gen(rd()); // rd()生成随机数种子

            // 生成一个在范围 [min, max] 内的随机数
            std::uniform_int_distribution<int> dis(min, max);

            return dis(gen);
        }

    public:
        Sort() // 构造
        {
            for (int i = 0; i < 100; i++)
            {
                nums.push_back(Myrandom(-100, 100));
            }
        }

        // 冒泡排序
        void BubbleSort()
        {
            // 每一次都将数组中最大(小)值移到最后面
            int n = nums.size();
            for (int i = 0; i < n - 1; i++) // 进行n-1次处理
            {
                for (int j = 1; j < n - i; j++)
                {
                    if (comp(nums[j], nums[j - 1]))
                    {
                        std::swap(nums[i], nums[j]);
                    }
                }
            }
        }

        // 选择排序
        void SelectSort()
        {
            // 每一次处理都是将最大(小)值放到数组的最前面
            int n = nums.size();
            for (int i = 0; i < n; i++)
            {
                int min_index = i;
                for (int j = i + 1; j < n; j++)
                {
                    if (comp(nums[j], nums[min_index]))
                        min_index = j;
                }
                std::swap(nums[min_index], nums[i]);
            }
        }

        // 插入排序
        void InsertSort()
        {
            int n = nums.size();
            for (int i = 1; i < n; i++)
            {
                for (int j = i; j > 0; j--)
                {
                    if (comp(nums[j], nums[j - 1]))
                    {
                        std::swap(nums[j], nums[j - 1]);
                    }
                    else
                        break;
                }
            }
        }

        // 希尔排序
        void ShellSort() // 本质就是在插入排序的基础上进行优化得来
        {
            // 先以gap距离为一组，分成gap组，进行预先的插入排序
            // 知道gap=1时即为完全插入排序（一定有序）
            int n = nums.size(), gap = n;

            while (gap > 1) // 最后一次使gap=1
            {
                gap = gap / 3 + 1;
                for (int i = gap; i < n; i++)
                {
                    for (int j = i; j >= gap; j -= gap)
                    {
                        if (comp(nums[j], nums[j - gap]))
                        {
                            std::swap(nums[j], nums[j - gap]);
                        }
                        else
                            break;
                    }
                }
            }
        }

        // 堆排序
        void adjust_down(int parent, int n) // 第二个参数是元素个数
        {
            int child = parent * 2 + 1;
            while (child < n)
            {
                // 先左孩子与右孩子作比较
                if (child + 1 < n && comp(nums[child], nums[child + 1]))
                {
                    child++;
                }
                // 父子节点比较
                if (comp(nums[parent], nums[child]))
                {
                    std::swap(nums[parent], nums[child]);
                    parent = child;
                    child = child * 2 + 1;
                }
                else
                    break;
            }
        }
        void HeapSort()
        {
            // 如果是升序
            // 先建立大根堆，然后依次进行与堆顶swap
            int n = nums.size();
            int parent = (n - 2) / 2; // 最后一个元素的下标是n-1
            for (int i = parent; i >= 0; i--)
            {
                adjust_down(i, n);
            }

            for (int i = n - 1; i > 0; i--)
            {
                std::swap(nums[0], nums[i]);
                adjust_down(0, i);
            }
        }

        // 快排
        // 1.hoare版本
        int PartSort1(int left, int right)
        {
            // 固定基准值，然后从两端向中间找基准值两侧的值
            int keyi = left;
            while (left < right)
            {
                // 右边找小的
                while (left < right && nums[keyi] <= nums[right])
                {
                    right--;
                }
                // 左边找大的
                while (left < right && nums[left] <= nums[keyi])
                {
                    left++;
                }
                std::swap(nums[left], nums[right]);
            }
            std::swap(nums[keyi], nums[left]);
            return left;
        }
        // 2.挖坑法
        int PartSort2(int left, int right)
        {
            int hole = left;
            int key = nums[left];
            while (left < right)
            {
                while (left < right && nums[right] >= key)
                {
                    right--;
                }
                nums[hole] = nums[right];
                hole = right;

                while (left < right && nums[left] <= key)
                {
                    left++;
                }
                nums[hole] = nums[left];
                hole = left;
            }
            nums[hole] = key;
            return hole;
        }
        // 3.前后指针法
        int PartSort3(int left, int right)
        {
            // 保证(pre,cur]区间内的值都大于key,最后一次key与nums[pre]交换
            int key = nums[left];
            int pre = left, cur = left + 1;
            while (cur <= right)
            {
                if (nums[cur] < key)
                {
                    // ++per指向的值大于key,大的和小的进行交换
                    std::swap(nums[cur], nums[++pre]);
                }
                cur++;
            }
            // pre指向的值小于key
            std::swap(nums[pre], nums[left]);
            return pre;
        }

        void QuickSort(int left, int right)
        {
            if (left >= right)
                return;
            int mid = PartSort1(left, right);
            QuickSort(left, mid - 1);
            QuickSort(mid + 1, right);
        }

        // 快排-三路划分
        void ThreeWayQuickSort(int left, int right)
        {
            if (left >= right)
                return;

            // 保证[left,cur]区间的只都是等于key的
            int key = nums[left];
            int l = left, r = right, cur = left;
            while (cur <= r)
            {
                if (nums[cur] > key)
                {
                    std::swap(nums[cur], nums[r]);
                    r--;
                }
                else if (nums[cur] < key)
                {
                    std::swap(nums[cur], nums[l]);
                    l++;
                    cur++;
                }
                else
                {
                    cur++;
                }
            }
            ThreeWayQuickSort(left, l - 1);
            ThreeWayQuickSort(r + 1, right);
        }

        // 归并排序
        void MergeSort(int left, int right)
        {
            if (left >= right)
                return;
            int mid = (left + right) / 2;
            MergeSort(left, mid);
            MergeSort(mid + 1, right);

            // 区间划分成
            int begin1 = left, end1 = mid;
            int begin2 = mid + 1, end2 = right;
            std::vector<int> tmp;
            tmp.reserve(right - left + 1);
            while (begin1 <= end1 && begin2 <= end2)
            {
                if (nums[begin1] < nums[begin2])
                {
                    tmp.push_back(nums[begin1++]);
                }
                else
                {
                    tmp.push_back(nums[begin2++]);
                }
            }
            while (begin1 <= end1)
            {
                tmp.push_back(nums[begin1++]);
            }
            while (begin2 <= end2)
            {
                tmp.push_back(nums[begin2++]);
            }
            memmove(&nums[left], &tmp[0], tmp.size() * sizeof(int));
        }

        size_t size()
        {
            return nums.size();
        }

    private:
        std::vector<int> nums;
        Comp comp;

    private:
        friend std::ostream &operator<<(std::ostream &out, const Sort<> &s);
    };

    std::ostream &operator<<(std::ostream &out, const Sort<> &s)
    {
        for (auto &it : s.nums)
        {
            out << it << ' ';
        }
        return out;
    }
}